package dynamicStudy;

public class NumberOfArithmeticSlices {

    /**
     * LeetCode T413 等差数列划分
     *
     * 数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
     *
     * 如果满足以下条件，则称子数组(P, Q)为等差数组：
     *
     * 元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
     *
     * 函数要返回数组 A 中所有为等差数组的子数组个数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/arithmetic-slices
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param args
     */
    public static void main(String[] args) {

    }

    public int numberOfArithmeticSlices(int[] nums) {
        if (nums == null || nums.length < 3){
            return 0;
        }
        int len = nums.length;
        //数组的状态为数量
        int[] dp = new int[len]; //默认初始化，所有的值都为0

        //进行遍历
        for (int i = 2; i < len; i++){
            int differ = nums[i] - nums[i - 1];
            //循环向前查找等差的数量，状态转移方程
            dp[i] = dp[i - 1];
            for (int j = i - 2; j >= 0; j--){
                if (nums[j + 1] - nums[j] == differ){
                    dp[i]++;
                } else {
                    break;
                }
            }
        }

        return dp[len - 1];

    }
}
